#define _CRT_SECURE_NO_WARNINGS 1
#include "heap1.h"

void HeapInit(Heap* hp)
{
	assert(hp);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}

void HeapDestory(Heap* hp)
{
	assert(hp && hp->_a);
	free(hp->_a);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}

Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType ret = *p1;
	*p1 = *p2;
	*p2 = ret;
}

void upsort(HPDataType* arr, int child)
{
	while (child > 0)
	{
		int parent = (child - 1) / 2;
		if (arr[parent] > arr[child])
		{
			Swap(&arr[parent], &arr[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->_capacity == hp->_size)
	{
		int newcapacity = hp->_capacity == 0 ? 4 : 2 * hp->_capacity;
		HPDataType * newarr = (HPDataType*)realloc(hp->_a, newcapacity * sizeof(HPDataType));
		if (newarr == NULL)
		{
			perror("realloc is faild");
			return -1;
		}
		hp->_a = newarr;
		hp->_capacity = newcapacity;
	}
	hp->_a[hp->_size++] = x;
	upsort(hp->_a, hp->_size - 1);
}

void downsort(HPDataType* arr, int size, int parent)
{
	int child = parent * 2 + 1;
	if (child+1 < size && arr[child] > arr[child + 1])
		child++;
	while (child < size)
	{
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(Heap* hp)
{
	assert(hp && hp->_size > 0);
	Swap(&hp->_a[0],&hp->_a[hp->_size - 1]);
	hp->_size--;
	downsort(hp->_a, hp->_size, 0);
}

HPDataType HeapTop(Heap* hp)
{
	assert(hp && hp->_a);
	return hp->_a[0];
}

int HeapSize(Heap* hp)
{
	assert(hp && hp->_a);
	return hp->_size;
}

bool HeapEmpty(Heap* hp)
{
	assert(hp && hp->_a);
	return hp->_size == 0;
}

void HeapSort(int* a, int ret)
{
	int n = ret;
	for (int i = 1; i < n; i++)
	{
		upsort(a, i);
	}
	while (n)
	{
		Swap(&a[0],&a[n - 1]);
		n--;
		downsort(a, n, 0);
	}
}